Ola Svensson, EPFL
Abstract:
We will discuss a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost.
We then overview the exciting and rapid development for TSP on graphic metrics following this approach: our 1.461-approximation algorithm, the better analysis by Mucha'11 yielding an approximation guarantee of 1.44, and the recent development by Sevo & Vygen'12 who gave a 1.4-approximation algorithm.
Finally, we point out some interesting open problems where our techniques currently fall short from generalizing to more general metrics.